package 剑指offer;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 队列的最大值
 */
public class Offer59_JZ64_2 {
    Queue<Integer> dataQueue = new LinkedList<>();
    LinkedList<Integer> maxQueue = new LinkedList<>();
    public Offer59_JZ64_2() {

    }

    public int max_value() {
        if (!maxQueue.isEmpty()) {
            return maxQueue.peekLast();
        }
        return -1;
    }

    public void push_back(int value) {
        dataQueue.offer(value);
        if (maxQueue.isEmpty() || value > maxQueue.peekLast()) {
            maxQueue.addLast(value);
        } else {
            maxQueue.addLast(maxQueue.peekLast());
        }
    }

    public int pop_front() {
        if (dataQueue.isEmpty()) {
            return -1;
        }
        maxQueue.removeFirst();
        return dataQueue.poll();
    }

    public static void main(String[] args) {
        Offer59_JZ64_2 demo = new Offer59_JZ64_2();
        demo.push_back(94);
        demo.push_back(16);
        demo.push_back(89);
        demo.pop_front();
        demo.push_back(22);
        demo.pop_front();
    }
}
